Concurrency Control in Spanner

In this lesson, we’ll learn how TrueTime guarantees correctness properties around concurrency control and how those properties ensure the following:

1. Externally consistent transactions

2. Reads from the past that do not block any ongoing transaction

3. Read-only transactions that do not require any lock

These features make it possible to ensure that at any time, t, the full database audit read will see the exact results of all transactions that are committed as of t.

We will use Paxos write and Spanner clients write to differentiate between both writes.

Timestamp management#

The implementation of Spanner supports reads from a snapshot and read-only and read-write transactions. The system implements the read-write transactions as standalone writes, whereas the read-only transactions are implemented as non-snapshot standalone reads. The following table shows the operation types Spanner supports and their respective concurrency control.

Read-only transactions#

The advantages of snapshot isolation are utilized by the read-only transaction. A read-only transaction requires pre-declaration of being read-only and not having any writes, since it is not a read-write transaction without any writes. Spanner executes reads within a read-only transaction without locking at a timestamp $t$ which is determined by the system. Executing the read at $t$ avoids blocking the incoming writes. This is an example of any suitably up-to-date replica that may handle the reads in a read-only transaction.

Once a timestamp has been chosen, the commit is unavoidable for both snapshot reads and read-only transactions. The commit does not happen if the data has been garbage collected at that timestamp. Therefore, clients can escape a retry loop's buffering of results by receiving them immediately. Clients can continue their queries on other servers if a server goes down by sending the same timestamp and reading location.

Paxos leader leases#

Timed leases are used in our Paxos implementation for sustainable leadership, that is, by default, 10 seconds. A node sends the request for timed lease votes to other participants to become a leader. When that node has a quorum of lease votes from other participants, it means it has the lease to become a leader.

For leader election, Paxos uses the Bully algorithm. If the proposer is not proposing to be a leader, any node can aim to be a leader. For a particular node to be accepted by the cluster, the node sends its server IDs to all peers within the cluster. The peers respond with their server ID. If all responses are smaller than the node's server ID, that node becomes the leader.

If a peer receives the ID of a node that wants to be a leader, and its ID is greater than the received ID, then instead of returning its ID, it starts an election to become the leader. The bully algorithm avoids livelock issues.

After a successful write, a replica's lease vote is automatically extended, and the leader will ask for a lease vote extension if it is about to expire. The lease interval of the leader starts when it receives the necessary number of votes to constitute a quorum, and the lease interval will end when the leader no longer has a quorum of votes. Within a Paxos group, a Paxos leader can change over time for different reasons. Spanner enforces a disjointness invariant, which implies that lease intervals of leaders are disjointed across all leaders of the shard over time.

Spanner implementation allows an abdication of a Paxos leader by freeing the lease votes of the participants. Spanner limits the conditions under which abdication is allowed to ensure that the disjointness invariant is maintained. The conditions are as follows:

• Consider that the Paxos leader defines the maximum timestamp as $S_{max}$.

• Before abdication, the Paxos leader should wait for $TT.after(s_{max})$.

The abdication of the Paxos leader is explained in the following slides:

To work, for each Paxos group, we require a disjointness invariant to be true, which means that the lease intervals of each Paxos group leader should be disjointed from other Paxos group leaders.

Read and write transactions#

The read and write transactions use two-phase locking. The timestamp can be assigned to a transaction after acquiring all locks and before releasing them. Spanner assigns a timestamp for any given transaction. Spanner enforces the following invariants:

1. The disjointness invariant

2. The external consistency invariant

Spanner assigns timestamps to Paxos writes in increasing order in each Paxos group. The assignment is in monotonically ordered across leaders too. The assignment of timestamps in monotonically ascending order is a simple task for a single leader replica. Using the disjointness invariant, all leaders must comply with this rule: a leader can assign timestamps only during their leader lease. It means when a timestamp $s$ is assigned to Paxos leader, $s_{max}$ is incremented to maintain disjointness.

In the external consistency invariant, if the $T2$ transaction is started after $T1$'s commit, we can infer from it that $T2$'s commit timestamp should be greater than $T1$'s commit timestamp. Consider the following for the transaction $T_{i}$:

• Start of $T_{i}$: $e_{i}^{start}$

• Commit of $T_{i}$: $e_{i}^{commit}$

• Commit timestamp of $T_{i}$: $s_{i}$

The $t_{abs}$ is the absolute of time, then the invariant becomes: if $t_{abs}(e_{1}^{commit}) < t_{abs}(e_{2}^{start})$ then $s_{1} < s_{2}$.

The following protocols are followed to assign timestamps to transactions. These protocols ensure the invariant is followed. The commit request's arrival event at the coordinator leader is $e_{i}^{server}$ for the write transaction $T_{i}$.

1. Start: The coordinator leader assigns a commit timestamp $s_{i}$ to $T_{i}$. The timestamp assigned is not less than the $TT.now().latest$, computed after $e_{i}^{server}$ (remember that $TT.now()$ provides an interval $[earliest, latest]$).

2. Commit wait: The coordinator leader waits until $TT.after(s_{i})$ or $TT.now().earliest > s_{i}$is true. After the wait, the client can see the updated data. The commit wait also makes sure that for $T_{i}$, $s_{i} < t_{abs}(e_{i}^{commit})$.

This is the monotonicity invariant that allows Spanner to reliably decide if a replica's state is up-to-date enough to fulfill a read. While traditional databases employ strict two-phase locking and single-version storage to guarantee external consistency. When traditional databases perform a "strong read," requesting the latest data, Spanner gains a read lock on the data, preventing any updates on the data that is part of the read transaction.

Serving reads at a timestamp#

Each replica in Spanner keeps track of the maximum timestamp, $t_{safe}$ , at which it was up-to-date. A read transaction at timestamp $t$ is considered successful if $t <= t_{safe}$ at any replica. Spanner defines $t_{safe}$ as follows:

where,

• $t_{safe}^{Paxos}$ is the safe time of each Paxos state machine or the latest Paxos write's timestamp. With respect to Paxos, incoming writes will no longer be committed at or below $t_{safe}^{Paxos}$ since timestamps are incremented monotonically, and write transactions are also committed in order.

• $t_{safe}^{TM}$ is the safe time of each transaction manager. For zero-prepared transactions, the value of $t_{safe}^{TM}$ is infinity. For these transactions, the state to be affected is indeterminate, and even the participant replica isn’t sure if these transactions will commit or not.

Note: For a participant, $t_{safe}^{TM}$ refers to the replica leader's transaction manager. The state of the transaction manager can be inferred by the participant via metadata transmitted with Paxos writes.

The commit protocol guarantees that all nodes know the lower bound of a prepared transaction's timestamp. As a result of the commit protocol, all participants involved in a transaction will be aware of the lower bound of the timestamp of prepared transactions.

As per the Spanner paper, for a group $g$ and a transaction $T_{i}$, every participant leader assigns a prepare timestamp, $s_{i,g}^{prepare}$ to its prepare record. The coordinator leader ensures that the commit timestamp of the transaction is greater than the prepare record for all participant groups $g$. This is for every replica in a group$g$, over all transactions $T_{i}$, prepared at $g$, $t_{safe}^{TM} = min_{i}(s_{i, g}^{prepare}) - 1$ over all transactions prepared at $g$.

Assigning timestamps to read-only transactions#

There are two stages of execution for a read-only transaction as per Spanner paper:

• Assign a timestamp $s_{read}$

• Execute the transaction's reads as snapshot reads at $s_{read}$

We can perform snapshot reads on those replicas that are up-to-date. $TT.now()$ returns TTinterval that contains the earliest and latest timestamp, which we will assign $s_{read} = TT.now().latest$ at any time after the start of a transaction. However, this timestamp may block data reads at $s_{read}$ if $t_{safe}$ hasn't advanced enough. To ensure disjointness, it is important to remember that picking a value for $s_{read}$ can also increase $s_{max}$. Because of this, Spanner should choose the oldest timestamp that maintains external consistency to minimize the possibility of blocking. In the next lesson, we will learn how to choose such a timestamp.

In this lesson, we learned how Spanner does concurrency control over read and write operations. Moreover, we learned how the read operations execute without locking at a timestamp chosen by the system and can only be executed on up-to-date replicas.